%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graph-theory-algorithms-book/
%%
%% Copyright (C) 2009--2011 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DontPrintSemicolon
\SetAlgoNoLine
%%
%% data section
\SetKwData{MyTrue}{True}
\SetKwData{NULL}{\footnotesize{NULL}}
%%
%% input
\KwIn{A binary tree $T$ on $n > 0$ vertices.}
%%
%% output
\KwOut{A list of the vertices of $T$ in in-order.}
\BlankLine
%%
%% algorithm body
$L \assign [\,]$\;
$S \assign$ empty stack\;
$v \assign$ root of $T$\;
\While{$\MyTrue$}{
  \If{$v \neq \NULL$}{
    $\push(S, v)$\;
    $v \assign$ left-child of $v$\;
  }
  \Else{
    \If{$\length(S) = 0$}{
      exit the loop\;
    }
    $v \assign \pop(S)$\;
    $\append(L, v)$\;
    $v \assign$ right-child of $v$\;
  }
}
\Return $L$\;
